/* 
 * Subsets
 */

#include "../func.h"

vector<vector<int>> subsets(vector<int> &S)
{
    sort(S.begin(), S.end());
    vector<vector<int>> result;
    vector<int> path;
    subsets(S, path, 0, result);
    return result;
}
void subsets(vector<int> &S, vector<int> &path, int step, vector<vector<int>> result)
{
    if (step == S.size())
    {
        result.push_back(path);
        return;
    }
    subsets(S, path, step + 1, result);
    path.push_back(S[step]);
    subsets(S, path, step + 1, result);
    path.pop_back();
}

vector<vector<int>> subsets(vector<int> &S)
{
    sort(S.begin(), S.end());
    vector<vector<int>> result(1);
    for (auto elem : S)
    {
        result.reserve(result.size() * 2);
        auto half = result.begin() + result.size();
        copy(result.begin(), half, back_inserter(result));
        for_each(half, result.end(), [&elem](decltype(result[0]) &e) {
            e.push_back(elem);
        });
    }

    return result;
}